package com.zyk.leetcode;

/**
 *
 * https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/
 *
 * @author zhangsan
 * @date 2021/4/3 21:22
 */
public class J10 {

    /** https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/ */
    public static int numWays(int n) {
        return process1(0, n);
    }

    private static int process1(int i, int n) {
        if(i >= n) {
            return i == n? 1: 0;
        }
        return (process1(i+1, n) + process1(i+2, n)) % 1000000007;
    }

    public static int dp(int n) {
        if(n == 0) {
            return 1;
        }
        if(n == 1 || n == 2 || n == 3) {
            return n;
        }
        int[] dp = new int[n+1];
        dp[n] = 1;
        dp[n-1] = 1;
        for (int i = n-2; i >= 0; i--) {
            dp[i] = (dp[i+1] + dp[i+2]) % 1000000007;
        }
        return dp[0];
    }


    // for test
    public static void main(String[] args) {
        int n = 2;
        int ans = numWays(n);
        System.out.println(ans);


        for (int i = 1; i <= 100; i++) {
            System.out.println(i + " : " + dp(i));
            System.out.println(i + " : " + numWays(i));
        }
    }

}
